home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d12 / v8n13.arc / HEAP.ASM < prev    next >
Encoding:
Assembly Source File  |  1989-06-10  |  12.7 KB  |  389 lines
  1.         title   HEAP.ASM  Simple MASM Heap manager
  2.         page    55,132
  3.  
  4. ; HEAP.ASM --- Simple Heap Manager for MASM Programs
  5. ; Copyright (C) 1989 Ziff Davis Communications
  6. ; PC Magazine * Ray Duncan
  7. ;
  8. ; To trade safety for speed, change the CHKPTRS equate.
  9. ;
  10. ; The routines in this module all assume that the 
  11. ; CPU direction flag is clear!!
  12.  
  13. true    equ     -1
  14. false   equ     0
  15.  
  16. chkptrs equ     true                    ; if true, HREALLOC and 
  17.                                         ; HFREE check all pointers
  18.  
  19. DGROUP  group   _DATA
  20.  
  21. _DATA   segment word public 'DATA'
  22.  
  23. hbase   dw      0                       ; base address of heap
  24. hsize   dw      0                       ; size of heap
  25.  
  26. _DATA   ends
  27.  
  28.  
  29. _TEXT   segment word public 'CODE'
  30.  
  31.         assume  cs:_TEXT,ds:DGROUP
  32.  
  33. ;
  34. ; HINIT:        initialize local heap
  35. ; 
  36. ; Call with:    AX      = size in bytes
  37. ;               DS:BX   = address of heap base
  38. ;
  39. ; Returns:      If function successful,
  40. ;               Carry   = clear
  41. ;
  42. ;               If function failed
  43. ;               Carry   = set
  44. ;
  45.         public  hinit
  46. hinit   proc    near
  47.  
  48.         cmp     ax,2                    ; check heap size
  49.         jbe     hinit1                  ; too small, return error
  50.         cmp     ax,32768
  51.         jae     hinit1                  ; too big, return error
  52.  
  53.         push    ax                      ; save registers
  54.         push    bx
  55.  
  56.         mov     hsize,ax                ; save heap size
  57.         mov     hbase,bx                ; save heap base address
  58.         sub     ax,2                    ; create header for block
  59.         mov     [bx],ax                 ; containing all free space
  60.         inc     ax
  61.         add     bx,ax                   ; set Carry if segment wrap
  62.  
  63.         pop     bx                      ; restore registers     
  64.         pop     ax
  65.         ret                             ; return to caller
  66.  
  67. hinit1: stc                             ; bad parameter,
  68.         ret                             ; return Carry = set
  69.  
  70. hinit   endp
  71.  
  72. ;
  73. ; HALLOC:       allocate block from local heap
  74. ;
  75. ; Call with:    AX      = requested block size
  76. ;
  77. ; Returns:      If function successful
  78. ;               Carry   = clear
  79. ;               DS:BX   = address of allocated block
  80. ;
  81. ;               If function unsuccessful
  82. ;               Carry   = set
  83. ;
  84.         public  halloc
  85. halloc  proc    near
  86.  
  87.         call    hfind                   ; try and allocate block
  88.         jnc     hal1                    ; jump if block was found
  89.  
  90.         call    hcoal                   ; coalesce free blocks
  91.         call    hfind                   ; try again to allocate
  92.  
  93. hal1:   ret                             ; return to caller
  94.  
  95. halloc  endp
  96.  
  97. ;
  98. ; HREALLOC:     resize previously allocated block
  99. ;
  100. ; Call with:    AX      = new requested block size
  101. ;               DS:BX   = address of existing block
  102. ;
  103. ; Returns:      If function successful
  104. ;               Carry   = clear
  105. ;               DS:BX   = address of resized block
  106. ;
  107. ;               If function unsuccessful
  108. ;               Carry   = set
  109. ;
  110.         public  hrealloc
  111. hrealloc proc   near
  112.  
  113.         push    ax                      ; save registers
  114.         push    cx
  115.         push    si
  116.         push    di
  117.         push    es
  118.  
  119.         if      chkptrs
  120.         call    hvalid                  ; check if valid pointer
  121.         jnc     hreal1                  ; pointer is OK
  122.         jmp     hreal6                  ; bad pointer, exit
  123.         endif
  124.  
  125. hreal1: mov     cx,ax                   ; save new requested size
  126.         mov     si,bx                   ; save block base address
  127.         mov     di,hbase                ; get address of heap end
  128.         add     di,hsize
  129.  
  130.         mov     ax,[si-2]               ; get current block size
  131.         and     ax,7fffh                ; remove in-use bit
  132.         cmp     cx,ax                   ; is block growing?
  133.         ja      hreal2                  ; yes, jump
  134.         je      hreal5                  ; no size change, exit
  135.  
  136.         sub     ax,cx                   ; block shrinking, find excess
  137.         cmp     ax,2                    ; enough for another header?
  138.         jb      hreal5                  ; no, leave block alone
  139.  
  140.         mov     [si-2],cx               ; shrink existing block
  141.         or      word ptr [si-2],8000h   ; and set in-use bit
  142.         add     si,cx                   ; create new block to hold
  143.         sub     ax,2                    ; the excess memory
  144.         mov     [si],ax
  145.         jmp     hreal5                  ; now exit
  146.  
  147. hreal2: call    hcoal                   ; coalesce free blocks
  148.  
  149.         add     si,ax                   ; get addr. of next block
  150.         cmp     si,di                   ; reached end of heap?
  151.         je      hreal4                  ; yes, jump
  152.  
  153.         test    word ptr [si],8000h     ; next block free?
  154.         jnz     hreal4                  ; no, must try elsewhere
  155.         add     ax,[si]                 ; yes, are combined blocks
  156.         add     ax,2                    ; large enough?
  157.         cmp     cx,ax
  158.         ja      hreal4                  ; no, jump
  159.  
  160.         mov     [bx-2],cx               ; update block header and
  161.         or      word ptr [bx-2],8000h   ; set in-use flag
  162.  
  163.         sub     ax,cx                   ; find excess memory
  164.         cmp     ax,2                    ; large enough for header?
  165.         jb      hreal3                  ; no, jump
  166.  
  167.         mov     si,bx                   ; create header for block
  168.         add     si,cx                   ; containing excess memory
  169.         sub     ax,2
  170.         mov     [si],ax
  171.         jmp     hreal5                  ; now exit
  172.  
  173. hreal3: add     ax,cx                   ; excess is 0 or 1 bytes,
  174.         mov     [bx-2],ax               ; fold it into the block
  175.         or      word ptr [bx-2],8000h
  176.         jmp     hreal5                  ; now exit
  177.  
  178. hreal4: mov     ax,cx                   ; look elsewhere for
  179.         mov     si,bx                   ; sufficiently large block
  180.         call    hfind
  181.         jc      hreal6                  ; none available, exit
  182.  
  183.         and     word ptr [si-2],7fffh   ; mark old block available
  184.         mov     cx,[si-2]               ; get its length for move
  185.         mov     di,bx                   ; copy old block to new
  186.         push    ds
  187.         pop     es
  188.         rep movsb
  189.  
  190. hreal5: clc                             ; successful reallocation,
  191.                                         ; return Carry = clear
  192.  
  193. hreal6: pop     es                      ; restore registers
  194.         pop     di
  195.         pop     si
  196.         pop     cx
  197.         pop     ax
  198.         ret                             ; return to caller
  199.  
  200. hrealloc endp
  201.  
  202. ;
  203. ; HFREE:        release heap block
  204. ; 
  205. ; Call with:    DS:BX   = block pointer
  206. ;
  207. ; Returns:      If CHKPTRS is FALSE
  208. ;               Nothing
  209. ;
  210. ;               If CHKPTRS is TRUE and pointer valid
  211. ;               Carry   = clear
  212. ;
  213. ;               If CHKPTRS is TRUE and pointer invalid
  214. ;               Carry   = set
  215. ;
  216.         public  hfree
  217. hfree   proc    near
  218.  
  219.         if      chkptrs
  220.         call    hvalid                  ; check if valid pointer
  221.         jc      hfree1                  ; jump if bad pointer
  222.         endif
  223.  
  224.         and     word ptr [bx-2],07fffh  ; turn off in-use flag
  225. hfree1: ret                             ; back to caller
  226.  
  227. hfree   endp
  228.  
  229. ;
  230. ; HFIND:        private subroutine for HALLOC and HREALLOC,
  231. ;               finds a free block in heap
  232. ;
  233. ; Call with:    AX      = requested block size
  234. ;
  235. ; Returns:      If function successful
  236. ;               Carry   = clear
  237. ;               DS:BX   = address of allocated block
  238. ;
  239. ;               If function unsuccessful
  240. ;               Carry   = set
  241. ;               
  242. hfind   proc    near
  243.  
  244.         push    ax                      ; save registers
  245.         push    cx
  246.         push    si
  247.         push    di
  248.  
  249.         mov     cx,ax                   ; save requested block size
  250.         mov     si,hbase                ; get heap base address
  251.         mov     di,si
  252.         add     di,hsize                ; get address of heap end
  253.         
  254. hfind1: lodsw                           ; pick up next block header
  255.         or      ax,ax                   ; this block free?
  256.         js      hfind2                  ; not free if bit 15 set, jump
  257.         cmp     ax,cx                   ; block free, large enough?
  258.         jae     hfind4                  ; size is adequate, jump
  259.  
  260. hfind2: and     ax,07fffh               ; go to next block
  261.         add     si,ax
  262.         cmp     si,di                   ; end of heap reached?
  263.         jne     hfind1                  ; not yet, try next block
  264.  
  265. hfind3: stc                             ; couldn't allocate block,
  266.         jmp     hfind7                  ; return Carry = set
  267.  
  268. hfind4: mov     bx,si                   ; save block base in BX
  269.         je      hfind6                  ; jump if exactly right size
  270.  
  271.         sub     ax,cx                   ; find excess amount
  272.         cmp     ax,2                    ; enough for another header?
  273.         jae     hfind5                  ; yes, jump
  274.  
  275.         add     ax,cx                   ; no, skip this block
  276.         jmp     hfind2
  277.  
  278. hfind5: add     si,cx                   ; subdivide existing block
  279.         sub     ax,2                    ; create header for free block
  280.         mov     [si],ax                 ; containing excess memory
  281.         
  282. hfind6: or      cx,8000h                ; set block size and in-use
  283.         mov     [bx-2],cx               ; flag, also clear Carry
  284.  
  285. hfind7: pop     di                      ; restore registers
  286.         pop     si
  287.         pop     cx
  288.         pop     ax                       
  289.         ret                             ; return to caller 
  290.  
  291. hfind   endp
  292.  
  293. ;
  294. ; HCOAL:        private subroutine for HALLOC and HREALLOC,
  295. ;               coalesces adjacent free blocks in heap
  296. ;
  297. ; Call with:    nothing
  298. ;
  299. ; Returns:      nothing
  300. ;
  301. hcoal   proc    near
  302.  
  303.         push    ax                      ; save registers
  304.         push    bx
  305.         push    si
  306.         push    di
  307.  
  308.         mov     bx,hbase                ; get heap base address
  309.         mov     di,bx
  310.         add     di,hsize                ; get heap end address
  311.         
  312. hcoal1: mov     si,bx                   ; point to block header
  313.  
  314. hcoal2: lodsw                           ; get length from header
  315.         mov     bx,ax                   ; calc. address of next block
  316.         and     bx,7fffh
  317.         add     bx,si
  318.         cmp     bx,di                   ; end of heap reached?
  319.         je      hcoal3                  ; yes, exit
  320.  
  321.         or      ax,ax                   ; not last block, is it free?
  322.         js      hcoal1                  ; not free if bit 15 set, jump
  323.  
  324.         test    word ptr [bx],8000h     ; next block free also?
  325.         jnz     hcoal1                  ; no, jump
  326.  
  327.         add     ax,[bx]                 ; merge two blocks together
  328.         add     ax,2
  329.         sub     si,2
  330.         mov     [si],ax                 ; update header of 1st block
  331.         jmp     hcoal2                  ; try for another merge
  332.  
  333. hcoal3: pop     di                      ; restore registers
  334.         pop     si
  335.         pop     bx
  336.         pop     ax
  337.         ret                             ; return to caller
  338.  
  339. hcoal   endp
  340.  
  341.         if      chkptrs
  342. ;
  343. ; HVALID:       tests whether a heap pointer is valid
  344. ;
  345. ; Call with:    DS:BX   = questionable pointer to block
  346. ;
  347. ; Returns:      If pointer is valid
  348. ;               Carry   = clear
  349. ;
  350. ;               If pointer is invalid
  351. ;               Carry   = set
  352. ;               
  353.         public  hvalid
  354. hvalid  proc    near
  355.  
  356.         push    ax                      ; save registers
  357.         push    si
  358.         push    di
  359.  
  360.         test    word ptr [bx-2],8000h   ; make sure already allocated
  361.         je      hval2                   ; no, pointer invalid
  362.  
  363.         mov     si,hbase                ; get heap base address
  364.         mov     di,si
  365.         add     di,hsize                ; get heap end address
  366.  
  367. hval1:  lodsw                           ; get length of this block
  368.         cmp     si,bx                   ; do pointers match?
  369.         je      hval3                   ; yes, jump (carry is clear)
  370.         and     ax,7fffh                ; strip in-use bit and
  371.         add     si,ax                   ; advance to next block
  372.         cmp     si,di                   ; end of heap?
  373.         jne     hval1                   ; no, try again
  374. hval2:  stc                             ; end of heap, pointer invalid
  375.  
  376. hval3:  pop     di                      ; restore registers
  377.         pop     si
  378.         pop     ax
  379.         ret                             ; return to caller
  380.  
  381. hvalid  endp
  382.         endif
  383.  
  384. _TEXT   ends
  385.  
  386.         end
  387.  
  388.  
  389.